#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mx = 1e6 + 5;

struct Edg{
    int u, v, w, nxt;
}edg[mx];

int CNT;
int head[mx];

void add_edg(int u, int v, int w = 1){
    edg[++CNT] = (Edg){u, v, w, head[u]};
    head[u] = CNT;
}

int n;
int a[mx];

namespace pts20{
    void solve(){
        int ans = 0;
        for(int x = 0; x < (1 << n + 1); x++){
            // cerr << x << '\n';
            // if(x == 32800) cerr << 1 << '\n';
            // if(x == 16416){
            //     cerr << (1ll << 15) << ' ' << (x & (1ll << 14)) << '\n';
            //     for(int i = 1; i <= n; i++){
            //         if(x & (1ll << i - 1)) cerr << i << ' ';
            //     }
            //     cerr << '\n';
            // }
            int res = 0;
            for(int i = 1; i <= n; i++){
                for(int j = i - 1; j; j--){
                    // if(x == 16416 && i == 15) cerr << j << "a\n";
                    // if(x == 16416 && i == 15) cerr << j << ' ' << (x & (1 << i - 1)) << ' ' << (x & (1 << j - 1)) << '\n';
                    if(((x & (1ll << i - 1)) && (x & (1ll << j - 1))) || (!(x & (1ll << i - 1)) && !(x & (1ll << j - 1)))){
                        if(a[i] == a[j]){
                            res += a[i];
                            // if(x == 32800) cerr << a[i] << '\n';
                            // if(a[i] == 13) cerr << 1;
                        }
                        break;
                    }
                }
            }
            ans = max(ans, res);
        }
        cout << ans << '\n';
        // cerr << '\n';
    }
}

namespace pts{
    int lst[mx], pre[mx], dp[2005][2005], pre1[2005];

    int calc(int l, int r){
        if(l == r) return 0;
        return pre[r] - pre[l];
    }

    void solve(){
        memset(pre, 0, sizeof(pre));
        memset(pre1, 0, sizeof(pre1));
        memset(dp, 0, sizeof(dp));
        pre[0] = 0;
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] + (a[i] == a[i - 1] ? a[i] : 0);
        }
        for(int i = 1; i <= n; i++){
            dp[i][0] = calc(1, i - 1);
            // cerr << dp[i][0] << ' ';
            for(int j = 1; j < i - 1; j++){
                dp[i][j] = pre1[j + 1] + calc(j + 1, i - 1) + (a[i] == a[j] ? a[i] : 0);
                // cerr << dp[i][j] << ' ';
                // for(int k = 0; k < j; k++){
                //     dp[i][j] = max(dp[i][j], dp[j + 1][k] + calc(j + 1,i - 1));
                // }
                // dp[i][j] += (a[i] == a[j] ? a[i] : 0);
            }
            if(i > 1) dp[i][i - 1] = max(dp[i - 1][i - 2], pre1[i - 1]) + (a[i] == a[i - 1] ? a[i] : 0);
            // cerr << dp[i][i - 1] << '\n';
            for(int j = 0; j < i - 1; j++) pre1[i] = max(pre1[i], dp[i][j]);
        }
        cout << max(dp[n][n - 1], pre1[n]) << '\n';
        // cerr << '\n';
    }
}

namespace pts100{
    int lst[mx], pre[mx], dp[mx], pre1[mx];

    int calc(int l, int r){
        if(l == r) return 0;
        return pre[r] - pre[l];
    }

    void solve(){
        memset(pre, 0, sizeof(pre));
        memset(pre1, 0, sizeof(pre1));
        memset(dp, 0, sizeof(dp));
        memset(lst, 0, sizeof(lst));
        for(int i = 1; i <= n; i++){
            lst[i] = pre[a[i]];
            pre[a[i]] = i;
        }
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] + (a[i] == a[i - 1] ? a[i] : 0);
        }
        cerr << pre[n] << '\n';
        for(int i = 1; i <= n; i++){
            cerr << pre1[0] << ' ' << pre1[a[i]] << ' ' << a[i] << ' ';
            dp[i] = pre1[0] - calc(i - 1, n);
            if(lst[i]) dp[i] = max(dp[i], pre1[a[i]] + a[i] - calc(i - 1, n));
            // dp[i] = max(pre1[0], pre1[a[i]] + a[i]) - calc(i - 1, n);
            dp[i] = max(dp[i], calc(1, i - 1));
            dp[i] = max(dp[i], dp[i - 1] + calc(i - 1, i));
            // if(i == 1) continue;
            pre1[0] = max(pre1[0], dp[i] + calc(i, n));
            pre1[a[i]] = max(pre1[a[i]], dp[i] + calc(i, n));
            cerr << dp[i] << '\n';
        }
        cout << dp[n] << '\n';
        cerr << '\n';
        // for(int i = 1; i <= n; i++){
        //     dp[i][0] = calc(1, i - 1);
        //     // cerr << dp[i][0] << ' ';
        //     for(int j = 1; j < i - 1; j++){
        //         dp[i][j] = pre1[j + 1] + calc(j + 1, i - 1) + (a[i] == a[j] ? a[i] : 0);
        //         // cerr << dp[i][j] << ' ';
        //         // for(int k = 0; k < j; k++){
        //         //     dp[i][j] = max(dp[i][j], dp[j + 1][k] + calc(j + 1,i - 1));
        //         // }
        //         // dp[i][j] += (a[i] == a[j] ? a[i] : 0);
        //     }
        //     if(i > 1) dp[i][i - 1] = max(dp[i - 1][i - 2], pre1[i - 1]) + (a[i] == a[i - 1] ? a[i] : 0);
        //     // cerr << dp[i][i - 1] << '\n';
        //     for(int j = 0; j < i - 1; j++) pre1[i] = max(pre1[i], dp[i][j]);
        // }
        // cout << max(dp[n][n - 1], pre1[n]) << '\n';
        // cerr << '\n';
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    // pts100::solve();
    if(n <= 15) pts20::solve();
    else if(n <= 2000) pts::solve();
}

signed main(){
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while(T--) solve();
}